package pyrachnid.model.pathFinderModel;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Set;
import java.util.Comparator;
import pyrachnid.model.ground_model.Cell;

public class Astar extends PathFind {
	private Hashtable<Noeud, Double> f = new Hashtable<Noeud, Double>();
	private Hashtable<Noeud, Double> g = new Hashtable<Noeud, Double>();
	private Hashtable<Noeud, Noeud> predecesseur;
	private Noeud x;
	private ArrayList<Noeud> ouverts,fermes;
	
	private ArrayList<Noeud> a_star(){
		ouverts = new ArrayList<Noeud>();
		fermes = new ArrayList<Noeud>();
		ouverts.add(m_source);
		g.put(m_source, 0.0);
		f.put(m_source, m_source.getDistance_cible());
		predecesseur = new Hashtable<Noeud, Noeud>();
		
		while(ouverts.size() != 0){
			x = noeud_de_arc_minimal(ouverts);
			fermes.add(x);
			ouverts.remove(x); // A verif
			
		
			if(x == m_target){
				ArrayList<Noeud> tabRetour =  new ArrayList<Noeud>();
				tabRetour.add(m_target);
				tabRetour.addAll(trajet(m_target,new ArrayList<Noeud>()));
				Collections.reverse(tabRetour);
				return tabRetour;
			}
			
			Set<Noeud> set = x.successeur().keySet();
			Noeud node;

		    Iterator<Noeud> itr = set.iterator();
		    while (itr.hasNext()) {
		      node = itr.next();
		      if((ouverts.contains(node) == false) && (fermes.contains(node) == false)){
		    	  predecesseur.put(node, x);
		    	  //System.out.println(node.getNomVille()+" predecesseur de "+x.getNomVille());
		    	  ouverts.add(node);
		    	  g.put(node, (g.get(x))+x.distance_avec(node));
		    	  f.put(node, (g.get(node))+node.getDistance_cible());
		      }else{
		    	  if(g.get(node)>g.get(x)){
		    		  g.put(node, (g.get(x))+x.distance_avec(node));
			    	  f.put(node, (g.get(node))+node.getDistance_cible());
			    	  if(fermes.contains(node)){
			    		  ouverts.add(node);
			    		  fermes.remove(node);
			    	  }
		    	  }
		      }
		    }
		}
		return new ArrayList<Noeud>();
	}
	
	private Noeud noeud_de_arc_minimal(ArrayList<Noeud> tab){
		return Collections.min(tab,
			new Comparator< Noeud >() {
				public int compare(Noeud a, Noeud b) {
					return (((Double)(a.getDistance_cible()+ f.get(a))).compareTo((Double) (b.getDistance_cible()+f.get(b))));
					}
				});
	}
	
	private ArrayList<Noeud> trajet(Noeud ville, ArrayList<Noeud> tab) {
		if(predecesseur.get(ville) == null) return tab;
		
		tab.add(predecesseur.get(ville));
		return trajet(predecesseur.get(ville), tab);
	}

	@Override
	protected ArrayList<Cell> compute() {
		ArrayList<Noeud> noeuds = this.a_star();
		ArrayList<Cell> cells = new ArrayList<Cell>();
		
		if(noeuds != null)
		{
			for(int i = 0; i < noeuds.size(); i++)
			{
				cells.add(noeuds.get(i).getCell());
			}
		}
		
		return cells;
	}

	@Override
	public PathFind clone() {
		return new Astar();
	}
}